The present invention relates to electronic digital logical circuitry, and, in particular, to a method and a circuit for the checking of the M out of N (M less than N) fixed-weight code which is useful in detecting error occurring during digital data transfers, communications, and storage.
An M out of N code (M less than N) is a fixed-weight code with a fixed number (M) of ones and a fixed number (N minus M) of zeros out of a total number (N) of word bits, or lines. The M out of N codes are useful because they can detect all unidirectional errors. Useful application for these codes are in digital data transfers, communications and storage. Additionally, these codes have been utilized in the arithmetic sections of digital computers, including the 2 out of 7 code in the IBM 650 and a 2 out of 5 code in the IBM 7070.
A check circuit for an M out of N code detects any single bit or unidirectional multibit error in an input, control, word. For an error to be undetected by such a check circuit, there must be an equal number of zero goes to one errors as one goes to zero errors. Fortunately, the probability of such offsetting error conditions is usually extremely small. An M out of N code checking circuit is defined to be "self-checked" whenever an error indiction will be derived whenever the input does not have the requisite N out of M bits set, or whenever a fault occurs with the logic of the checker circuit itself.
In general, prior art code checkers are comprised of AND and OR gate logics and assume a multiplicity of forms dependent upon which N out of which M is specified to be checked. One code checker of regular form is for checking for N/2 out of N bits. This is, of course, a restricted case wherein M=1/2N, and the N input bits must be divided into two equally sized groups for implementation.
A prior art reference to the design of M out of N code checkers occurs in the article EFFICIENT DESIGN OF SELF-CHECKING CHECKERS FOR M-OUT-OF-N CODES by M. A. Marouf and A. D. Friedman occurring in Conference Proceedings for the 1977 IEEE International Conference on Fault-Tolerant Computing at pp. 143-149. A generalized, flow-charted, procedure for the efficient generation and design of M out of N code checkers from logical AND and OR gates is given in this reference. Each of the code checkers so derived is unique, that is it sufficies for a unique N and a unique M. The procedures advanced are indicated to be efficient in terms of hardware cost and the complexity of the design method. For the case of 2M+2 less than or equal to N less than or equal to 4M, M greater than or equal to 2, the preferred realization procedure for the specific case of M=3 and N=8 requires 40 gates. For another specific case wherein N=2M+1, M greater than or equal to 2 (thereby checking an M-out-of-(2M+1) code) the preferred realization procedure develops a checker of 61 gates. The procedures for deriving M out of N code checkers, and the code checker circuits so derived are, in general, multilevel and non-trivial of design implementation.
As a preferred, subcircuit, part to the overall invention of an M out of N code checker circuit, a particular circuit for the generation of berger codes utilizing the exclusive OR logical element, and particularly the Complementary Metal Oxide Semiconductor (CMOS) technology transfer gate element in the realization of such exclusive OR logical element, will be taught. A berger code is defined as the binary encoded number of binary ones occurring between N=3 input signals, and is old in the art. A berger code generator circuit for the binary encoding upon two output signal lines of the number of binary ones occurring upon three input signal lines is trivial of implementation from digital AND, OR, and INVERTER gates and may thusly not be expressly referenced in the prior art of code generator circuits. The preferred embodiment berger code generator circuit to the present invention utilizes an integral exclusive OR logical element implemented from CMOS transfer gates, and not merely the exclusive OR logical function as implemented from the logical elements of AND, OR, and INVERTER gates as occurs in TTL MSI industry standard logic component 86. A preferred prior art reference to the implementation of the exclusive OR (and exclusive NOR) logical element(s) from CMOS transfer gates occurs in U.S. patent application, Ser. No. 355,804 now U.S. Pat. No. 4,477,904 titled Parity Generation/Detection Logic Circuit from Transfer Gates to Lee Thorsrud. An alternative prior art reference to the implementation of the exclusive OR (and exclusive NOR) logical element(s) from CMOS transfer gates occurs in U.S. Pat. No. 4,424,460 issued Jan. 3, 1984 titled APPARATUS AND METHOD FOR PROVIDING A LOGICAL EXCLUSIVE OR/EXCLUSIVE NOR FUNCTION to David W. Best. A prior art reference to the implementation of the exclusive OR (and exclusive NOR) logical element(s) from transistors occurs in U.S. Pat. No. 4,041,376 issued Aug. 9, 1977 titled HIGH SPEED COMPLEMENTARY OUTPUT EXCLUSIVE OR/NOR CIRCUIT to Barry J. Robinson. This prior art reference teaches the utility of CMOS transfer gates in the generation of parity code bits, but is not concerned with berger codes.